1. Field
Example embodiments relate to a fast stochastic decoding method for a low density parity check (LDPC) code, and more particularly, to a decoding method that may reduce a number of iterations of decoding, using a new variable mode updating method.
2. Description of the Related Art
A low density parity check (LDPC) code, which is an error correction code, has provided performance similar to the channel capacity of Shannon by utilizing a message passing algorithm, such as a belief propagation (BP) algorithm. However, embodying hardware of a decoder of the LDPC code is a complex matter. A stochastic computation scheme has been used as one of schemes to embody a low precision digital circuit, and expresses a probability value by a bit stream and thus, a floating point operation may be performed using a binary operation.
A BP decoder uses a message expressed by the floating point and thus, a complexity in embodying the decoder increases and routing congestion occurs.
Recently, the stochastic decoder among LDPC decoders has been drawing attention. The stochastic decoder stochastically converts, based on a density of bit 1, a message probability value used in a conventional BP decoder to a bit stream corresponding to the probability value of the message and thus, has a structure enabling a binary operation and has a feature of increasing a decoding speed and decreasing an operation complexity. To overcome the deficiencies of the conventional BP decoder, the stochastic decoder embodies a parity check node and a variable node using a binary operator, by applying the stochastic computation scheme and thus, allows a high-speed decoding with a low complexity. The stochastic decoder converts a single message to a binary bit stream and thus, may perform a greater number of iterations of decoding than the conventional BP decoder.
The LDPC code was proposed by Robert G. Gallager in 1962. Although the LDPC shows performance similar to the channel capacity of Shannon, the LDPC code has been ignored until recent due to a high complexity in embodying a decoder, and studies on the LDPC are now actively conducted. In a parity check matrix of the LDPC code, a number of ‘1’ is relatively small.
FIG. 1 illustrates a parity check matrix of an LDPC code.
Referring to FIG. 1, in a matrix 100 of M×N, N may denote a number of columns and may be the same as a length of a codeword, and M may denote a number of rows and may be the same as a number of parity check equations.
FIG. 2 illustrates a parity check matrix of an LDPC code, expressed in a Tanner graph.
Referring to FIG. 2, circles 201, 202, 203, 204, 205, 206, and 207 may denote variable nodes and may indicate columns in the matrix 100. Squares 211, 212, and 213 may denote check nodes and may indicate rows in the matrix 100. Each node may be connected by an edge with each other. The edge may be dependent (determined based) on a location of an element that is different from ‘0’ in the matrix 100. When a check node i and a check node j are connected by an edge, an element hij may have a value different from ‘0’ in the matrix 100. A number of edges connected to a node is referred to as a degree of the node. When the variable node has a constant degree of dv and the check node has a constant degree of dc, the LDPC code may be referred to as a regular LDPC code. When the degree of the variable node and/or the degree of the check node are not constant, the LDPC code may be referred to as an irregular LDPC code.
The LDPC code is decoded to obtain, from a signal r received from a channel, a codeword c satisfying a condition of Equation 1. cH=0  [Equation 1]
The BP decoder performs decoding by exchanging a message through an edge that connects a variable node with a parity check node, as one of message passing algorithms. In the present example, operations performed in each node may be referred to as a node updating process. During the decoding iteration process, each node may exchange messages with neighbors connected by edges, using the messages received from the previous iteration process. A message of parity check node ci expressed by probability values may be updated as expressed by Equation 2.pci=pv1(1−pv2)+(1−pv1)Pv2  [Equation 2]
FIG. 3 illustrates an example of parity check node updating.
Referring to FIG. 3, V1 and V2 may be variable nodes adjacent to a parity check node ci. A variable node vi may be updated as expressed by Equation 3.
                              p                      v            i                          =                                            p                              c                1                                      ⁢                          p                              c                2                                                                                        p                                  c                  1                                            ⁢                              p                                  c                  2                                                      +                                          (                                  1                  -                                      p                                          c                      1                                                                      )                            ⁢                              (                                  1                  -                                      p                                          c                      2                                                                      )                                                                        [                  Equation          ⁢                                          ⁢          3                ]            
FIG. 4 illustrates an example of a variable node updating.
Referring to FIG. 4 and Equation 3, C1 and C2 may be parity check nodes adjacent to the variable node.
When a probability value to be used for updating a parity check node and a variable node of the BP decoder is calculated, a complex circuit that is capable of performing floating point operations, while embodying hardware, may be used. A stochastic computation scheme applies a probability value in a range of [0, 1] to infinite in a Bernoulli sequence and thus, may easily calculate the probability value.
FIG. 5 illustrates a multiplication of two probability values, and the multiplication is expressed, by a logical AND operator 500, using stochastic computation.
Referring to FIG. 5, each probability value may be the same as a value obtained by dividing a number of ‘1’ in a bit stream by a length of the bit stream. A stochastic decoder may use a bit stream corresponding to a probability value as a message and thus, may update each node using the logical AND operator 500.
FIG. 6 illustrates the check node updating of FIG. 3, using a logical XOR operator 600.
Referring to FIG. 6, the parity check node updating of FIG. 3 may be performed by the XOR operator 600.
FIG. 7 illustrates the variable node updating of FIG. 4, using two logical AND operators 710 and 720 and a JK flip-flop 730.
Referring to FIG. 7, the variable node updating of FIG. 4 may be performed by the two logical AND operators 710 and 720 and the JK flip-flop 730.
When all input message bits received from neighbor parity check nodes and a channel are the same, variable node updating based on a stochastic computation scheme may be updated to the same bit, otherwise and when at least one of the input message bits received from neighbor parity check nodes and a channel is different variable node updating may be in a hold state. The hold state may suppress message exchanging, thereby leading to performance deterioration of the decoder, and may increase a number of iterations of decoding for successful decoding.
An edge memory proposed by Tehrani selects an appropriate bit from among past messages stored in a memory when the updating is in the hold state and thus, may show performance similar to the BP decoder. However, the scheme may perform a greater number of iterations of decoding, compared with the BP decoder.